package com.Offer;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

/*
    面试题38：字符串的排列
    题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。
    例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba.
 */
public class demo38 {
    public static void main(String[] args) {
/*        String s = "abc";
        ArrayList<String> permutation = Permutation(s);
        permutation.forEach(System.out::println);*/
        int[] input = new int[]{1,2,3};
        helper1(0,input);
    }

    public static ArrayList<String> Permutation(String str){
        ArrayList<String> res = new ArrayList<>();
        if(str == null || str.length() == 0){
            return res;
        }
        helper(res,0,str.toCharArray());
        Collections.sort(res);
        return res;
    }

    public static void helper(ArrayList<String> res,int index,char[] s){
        if(index == s.length-1){
            res.add(String.valueOf(s));
            return;
        }
        for(int i = index;i<s.length;i++){
            if(i == index || s[index] != s[i]){
                swap(s,index,i);
                helper(res,index+1,s);
                swap(s,index,i);
            }
        }
    }

    public static void swap(char[] c,int a,int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }

    //----------------------------------------------------------------

    public static void helper1(int index,int[] input){
        if(index == input.length){
            for (int i = 0; i < input.length; i++) {
                System.out.print(input[i]+" ");
            }
            System.out.println();
            return;
        }
        for(int i = index;i<input.length;i++){
            if(i == index || input[i] != input[index]){
                swap1(input,i,index);
                helper1(index+1,input);
                swap1(input,i,index);
            }
        }
    }

    public static void swap1(int[] input,int a,int b){
        int t = input[a];
        input[a] = input[b];
        input[b] = t;
    }

}
